// 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

// 你应当保留两个分区中每个节点的初始相对位置。

// 示例:

// 输入: head = 1->4->3->2->5->2, x = 3
// 输出: 1->2->2->4->3->5


// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 先找到第一个节点值大于等于x的节点pre，后面所有的节点值小于x的节点都放在后面
class Solution1 {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy = new ListNode{0};
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        // 找到第一个节点值大于等于x的节点前一个节点，定为pre节点
        while (pre->next && pre->next->val < x) pre = pre->next;
        cur = pre;
        while (cur->next) {
            if (cur->next->val >= x) {
                cur = cur->next;
            } else {
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = pre->next;
                pre->next = tmp;
                pre = pre->next;
            }
        }
        return dummy->next;
    }
};

// 新建一条链表，存放的全都是节点值小于x的节点
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *dummy = new ListNode(-1); // 原链表的虚假头节点
        dummy->next = head;
        ListNode *res = new ListNode(-1); // 最终链表的虚假头节点
        ListNode *cur = dummy;
        ListNode *pre = res;
        while (cur->next) {
            if (cur->next->val < x) { // 小于x的节点组成一个小值链表
                pre->next = cur->next;
                pre = pre->next;
                cur->next = cur->next->next;
                pre->next = nullptr;
            } else
                cur = cur->next;
        }
        pre->next = dummy->next;
        return res->next;
    }
};